package fun.coding.leetcode;

public class LongestPalindromicSubstring {

	public static void main(String[] args) {
		LongestPalindromicSubstring ins = new LongestPalindromicSubstring();
		System.out.println(ins.longestPalindrome("abb"));
	}
	
	// Using DP is O(N^2) time and O(N^2) space
	// For two strings using DP, we normally have a 2 dimensional array
	// For this problem only one string, we still use a 2-dimensional array
	// state: lookup[i][j] substring i, j (inclusive) is a palindrome or not
	// function: f[i][j] = s(i) == s(j) ? f[i+1][j-1] : false
	// initial state: for length = 1, always true, for length = 2, if same, true
	// There is an O(N) algorithm: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
	public String longestPalindromeDP(String s) {
		if (s == null || s.length() == 0) return null;
		
		boolean[][] lookup = new boolean[s.length()][s.length()];
		
		int maxLength = 1;
		int start = 0;
		int end = 0;
		
		for (int i = 0; i < s.length(); i++) {
			lookup[i][i] = true;
		}
		
		for (int i = 0; i + 1 < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i + 1)) lookup[i][i+1] = true;
			
			if (lookup[i][i+1] && 2 > maxLength) {
				maxLength = 2;
				start = i;
				end = i + 1;
			}
		}
		
		// For each length, bottom up way to build up the lookup table
		for (int i = 3; i <= s.length(); i++) {
			// Do a sliding window scan
			for (int j = 0; j + i < s.length() + 1; j++) {
				int l = j;
				int r = j + i - 1;
				lookup[l][r] = (s.charAt(l) == s.charAt(r)) ? lookup[l+1][r-1] : false;
				if (lookup[l][r] && i > maxLength) {
					maxLength = i;
					start = l;
					end = r;
				}
			}
		}
		return s.substring(start, end + 1);
	}
	
	
	// This is O(N^2) solution, for each element as the middle, starting from the middle, and goes left and right
	// The brute force one is O(N^3), for each length, sliding window O(N^2), and palindrome check adds another N
	// Another way think about the brute force: 
	// The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. 
	// There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).
	// http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
	public String longestPalindrome(String s) {
		if (s == null || s.length() == 0) return null;
		int max = 0;
		String maxString = "";
		
		for (int i = 0; i < s.length(); i++) {
			// assume odd
			String odd = this.expandString(s, i - 1, i + 1);
			
			if (odd.length() > max) {
				max = odd.length();
				maxString = odd;
			}
			
			// assume even
			String even = this.expandString(s, i, i + 1);
			
			if (even.length() > max) {
				max = even.length();
				maxString = even;
			}
		}
		return maxString;
	}
	
	private String expandString(String s, int l, int r) {
		while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
			l--;
			r++;
		}
		return s.substring(l + 1, r);
	}
	
	/* this is O(N) solution  http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
	public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int length = s.length();    
        int max = 0;
        String result = "";
        for(int i = 1; i <= 2 * length - 1; i++){
            int count = 1;
            while(i - count >= 0 && i + count <= 2 * length  && get(s, i - count) == get(s, i + count)){
                count++;
            }
            count--; // there will be one extra count for the outbound #
            if(count > max) {
                result = s.substring((i - count) / 2, (i + count) / 2);
                max = count;
            }
        }
        
        return result;
    }
    
    private char get(String s, int i) {
        if(i % 2 == 0)
            return '#';
        else 
            return s.charAt(i / 2);
    }
	*/
}
